#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2020年03月13日
版    本：v1.0.0
描    述：
Copyright (C) 2020 All rights reserved.
'''


"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""


class Solution:
    """
    @param root: param root: The root of the binary search tree
    @param k1: An integer
    @param k2: An integer
    @return: return: Return all keys that k1<=key<=k2 in ascending order
    """

    def __init__(self):
        self.result = list()

    def searchRange(self, root, k1, k2):
        self.helper(root, k1, k2)
        return self.result

    def helper(self, root, k1, k2):
        if not root:
            return

        if root.val > k1:
            self.helper(root.left, k1, k2)

        if root.val >= k1 and root.val <= k2:
            self.result.append(root.val)

        if root.val < k2:
            self.helper(root.right, k1, k2)
